#ifndef __TA234COM_H_
#define __TA234COM_H_

#include "tcomplejo.h"
#include "tlistacom.h"

//! \file ta234com.h
//! \brief Cabeceras de la clase TA234Com, TA234Nodo y TA234ColoNodo

class TA234Nodo;

//! \class TA234Com
/*!	\brief Clase que implementa un árbol 234*/
class TA234Com
{
	friend class TA234Nodo;
 	
 	public:	 	
		//! \brief Constructor por defecto de TA234Com
		/*!	Construye un arbol 234 vacio*/
		TA234Com();
		//! \brief Constructor de copia de TA234Com
		/*!	Construye un árbol 234 copia de otro*/
		TA234Com(const TA234Com &);
		//! \brief Destructor de TA234Com
		/*!	Libera la memoria ocupada del árbol AVL*/
		~TA234Com();
		//! \brief Operador =
		/*!	Asigna un árbol 234 a otro*/
		TA234Com& operator=(const TA234Com &);
		//! \brief Operador ==
		/*!	Devuelve verdadero si ambos árboles son iguales*/
		bool operator==(const TA234Com &) const;
		//! \brief Operador != 
		/*!	Devuelve verdadero si los árboles son distintos*/
		bool operator!=(const TA234Com &a) const{ return !operator==(a);};
		//! \brief EsVacio
		/*!	Devuelve true si el árbol 234 está vacio*/
		bool EsVacio() const ;
		//! \brief Insertar
		/*!	Inserta un TComplejo en el árbol y devuelve true si lo consigue*/
		bool Insertar(const TComplejo &);
		//! \brief Buscar
		/*!	Devuelve true si el TComplejo ha sido previamente insertado*/
		bool Buscar(const TComplejo&) const;
		//! \brief Altura
		/*!	Devuelve la altura del árbol (niveles que tendra)*/
		int Altura() const ;
		//! \brief Nodos
		/*!	Devuelve el número de nodos del árbol*/
		int Nodos() const;
		//! \brief NodosHoja
		/*!	Devuelve el número de nodos del árbol sin hijos*/
		int NodosHoja() const;
		//! \brief Niveles
		/*!	Devuelve el recorrido por niveles del árbol*/
		TListaCom Niveles() const;
		//! \brief Inorden
		/*!	Devuelve el recorrido Inorden del árbol*/
		TListaCom Inorden() const;
		//! \brief Borrar
		/*!	Borra un TComplejo y devuelve true si lo consigue*/
		bool Borrar(const TComplejo&);
		
		bool Comprobar();
			
	private:
		//! \brief TA234Nodo *raiz
		/*!	Raíz del arbol AVL*/
		TA234Nodo *raiz;
		//! \brief NivelesAux
		/*!	Método privado que devuelve el recorrido niveles en la lista pasada como argumento*/
		void NivelesAux(TListaCom&) const;
		//! \brief InordenAux
		/*!	Método privado que devuelve el recorrido Inorden en la lista pasada como argumento*/
		void InordenAux(TListaCom&) const;
};

//! \class TA234Nodo
/*!	\brief Clase que implementa un nodo de un árbol 234*/
class TA234Nodo
{
	friend class TA234Com;
	public:
	
		//! \brief Constructor por defecto de TA234Nodo
		/*!	Construye un nodo de árbol 234*/
		TA234Nodo();
		//! \brief Constructor de copia de TA234Nodo
		/*!	Construye un nodo de árbol 234 copia de otro*/
		TA234Nodo(const TA234Nodo&);
		//! \brief Destructor de TA234Nodo
		/*!	Libera la memoria de un nodo*/
		~TA234Nodo();
		//! \brief Operador = 
		/*!	Asigna T234Nodo*/
		TA234Nodo& operator=(const TA234Nodo&);
		//! \brief Operador == 
		/*!	Compara dos T234Nodo*/
		bool operator==(const TA234Nodo&) const;
		
		
	private:	
		//! \brief TComplejo item
		/*!	Dato que almacena el nodo*/
		int numitem;
		//! \brief TComplejo itIz
		/*!	Item izquierdo del nodo*/
		TComplejo itIz;
		//! \brief TComplejo itDe
		/*!	Item derecho del nodo*/
		TComplejo itDe;
		//! \brief TComplejo itMe
		/*!	Item medio del nodo*/
		TComplejo itMe;
		//! \brief TA234Com hijoIz, hijoMeIz,hijoMeDe, hijoDe
		/*!	Hijos del nodo*/
		TA234Com hijoIz, hijoMeIz, hijoMeDe, hijoDe;
		//! \brief bool eshoja
		/*!	Comprueba si el nodo tiene o no hijos*/ 
		bool eshoja;
		//! \brief Divide2
		/*!	Divide un 4-nodo hijo de un 2-nodo. El entero indica cual de
		 * los 2 hijos hay que dividir.*/
		void Divide2(const int);
		//! \brief Divide3
		/*!	Divide un 4-nodo hijo de un 3-nodo. El entero indica cual de
		 * los 3 hijos hay que dividir.*/
		void Divide3(const int);
		//! \brief DivideRaiz
		/*!	Divide la raiz*/
		void DivideRaiz();
		//! \brief Combina2
		/*!	Combina la raiz en caso de ser un 2-nodo con hijos 2-nodo*/
		void Combina2();
		//! \brief Reestructurar
		/*!	Combinaciones y rotaciones del borrado. Se realiza desde el 
		 * padre, indicando el hijo mediante el entero, y avanzando el
		 * puntero del recorrido de borrado*/
		void Reestructurar(int, TA234Nodo*&);
		//! \brief MayorIzquierda
		/*!	Devuelve el item mayor del hijo iquierda*/
		const TComplejo MayorIzquierda(const int, TComplejo);
};

class TA234ColaNodo;

//! \class TA234Cola
/*!	\brief Clase que implementa una cola de punteros a TA234Nodo*/
class TA234Cola
{
	public:
		//! \brief Constructor por defecto de TA234Cola
		/*!	Crea una cola de punteros a TA234Nodo vacía*/
		TA234Cola():principio(NULL), fin(NULL){};
		//! \brief Destructor de TA234Cola
		/*!	Libera la memoria de una cola*/
		~TA234Cola();
		//! \brief Encolar
		/*!	Añade un puntero a TA234Com al final de la cola*/
		void Encolar(const TA234Com* a);
		//! \brief EsVacia
		/*!	Devuelve true si la cola es vacía*/
		TA234Com* Desencolar();
		//! \brief Desencolar
		/*!	Borra el primer elemento de la cola*/
		bool Esvacia(){return principio==NULL;};
		
	private:
		//! \brief TA234CNodo* principio
		/*!	Cabeza de la cola*/
		TA234ColaNodo *principio;
		//! \brief TA234CNodo* fin
		/*!	Final de la cola*/
	
		TA234ColaNodo *fin;
};



//! \class TA234ColaNodo
/*!	\brief Clase que implementa un nodo de cola de punteros a T234Com*/
class TA234ColaNodo
{
	friend class TA234Cola;
	public:
		//! \brief Constructor por defecto de TA234ColaNodo
		/*!	Crea un nodo de cola de punteros a TA234ColaNodo vacío*/
		TA234ColaNodo():n(NULL),sig(NULL){};
		//! \brief Constructor sobrecargado de TA234ColaNodo
		/*!	Crea un nodo de cola de punteros a TA234ColaNodo con el puntero a árbol a*/
		TA234ColaNodo(TA234Com* a):n(a),sig(NULL){};
		//! \brief Constructor de copia TA234ColaNodo
		/*!	Crea un nodo de cola de punteros a TA234ColaNodo copia de otro*/
		TA234ColaNodo(const TA234ColaNodo& nodo);
		//! \brief Destructor de TA234ColaNodo
		/*! Libera la memoria de un nodo*/
		~TA234ColaNodo();
		
	private:
		//! \brief TA234ColaNodo* n
		/*!	Puntero a árbol que almacenamos*/
		TA234Com *n;
		//! \brief TA234ColaNodo* sig
		/*!	Siguiente elemento de la cola*/
		TA234ColaNodo *sig;
};



#endif
